package edu.rpi.cs.webgraph.graphfragment;

import java.util.Collection;
import java.util.HashMap;

/**
 * Author: josh
 * Date: Mar 3, 2009
 * Time: 9:58:54 AM
 */
public class FragmentMatcher<N, E> {
    public class Match extends HashMap<N, N> {

        public Match() {
            super();
        }
    }

    public boolean findFirstMatch(final GraphWrapper<N, E> target,
                                  final GraphWrapper<N, E> fragment,
                                  final Match alreadyMatched) {
        for (N f : fragment.getNodes()) {
            // Choose an unmatched fragment node.
            if (alreadyMatched.containsKey(f)) {
                continue;
            }

            Collection<N> fIn = fragment.getInEdges().get(f);
            Collection<N> fOut = fragment.getOutEdges().get(f);

            for (N g : target.getNodes()) {
                // Choose an unmatched target node.
                if (alreadyMatched.containsValue(g)) {
                    continue;
                }

                // Fragment node must have the same number of incident edges as
                // the target node.
                Collection<N> gIn = target.getInEdges().get(g);
                Collection<N> gOut = target.getOutEdges().get(g);
                if (gIn.size() != fIn.size()) {
                    continue;
                }
                if (gOut.size() != fOut.size()) {
                    continue;
                }

                boolean good;

                // Matched outbound edges of the fragment must align with
                // those of the target graph.
                good = true;
                for (N fn : fOut) {
                    N gn = alreadyMatched.get(fn);
                    if (null != gn && !target.areAdjacent(g, gn)) {
                        good = false;
                        break;
                    }
                }
                if (!good) {
                    continue;
                }

                // Matched inbound edges of the fragment must align with
                // those of the target graph.
                good = true;
                for (N fn : fIn) {
                    N gn = alreadyMatched.get(fn);
                    if (null != gn && !target.areAdjacent(gn, g)) {
                        good = false;
                        break;
                    }
                }
                if (!good) {
                    continue;
                }

                // Recurse.
                alreadyMatched.put(f, g);
                if (findFirstMatch(target, fragment, alreadyMatched)) {
                    return true;
                }
                alreadyMatched.remove(f);
            }
        }

        return false;
    }
    
    public boolean findFirstApproxMatch(final GraphWrapper<N, E> target,
    		final GraphWrapper<N, E> fragment,
    		final Match alreadyMatched) {
    	for (N f : fragment.getNodes()) {
    		// Choose an unmatched fragment node.
    		if (alreadyMatched.containsKey(f)) {
    			continue;
    		}

    		Collection<N> fIn = fragment.getInEdges().get(f);
    		Collection<N> fOut = fragment.getOutEdges().get(f);

    		for (N g : target.getNodes()) {
    			// Choose an unmatched target node.
    			if (alreadyMatched.containsValue(g)) {
    				continue;
    			}

    			// Fragment node must have the same number of incident edges as
    			// the target node.
    			Collection<N> gIn = target.getInEdges().get(g);
    			Collection<N> gOut = target.getOutEdges().get(g);
    			if (gIn.size() != fIn.size()) {
    				continue;
    			}
    			if (gOut.size() != fOut.size()) {
    				continue;
    			}
    			boolean good;
    			
    			/*This is an approximate matching algorithm.*/
    			
    			// Matched outbound edges of the fragment must align with
    			// those of the target graph.
    			good = true;
    			double failed = 0;
    			double total = 0;
    			for (N fn : fOut) {
    				N gn = alreadyMatched.get(fn);
    				total++;
    				if (null != gn && !target.areAdjacent(g, gn)) {
    					failed++;
    				}
    			}
    			double tolerance = tolerance(total);
    			good = (failed / total) <= tolerance;
    			if (!good) {
    				continue;
    			}
    			// Matched inbound edges of the fragment must align with
    			// those of the target graph.
    			good = true;
    			failed = 0;
    			total = 0;
    			for (N fn : fOut) {
    				N gn = alreadyMatched.get(fn);
    				total++;
    				if (null != gn && !target.areAdjacent(g, gn)) {
    					failed++;
    				}
    			}
    			tolerance = tolerance(total);
    			good = (failed / total) <= tolerance;
    			if (!good) {
    				continue;
    			}
    			// Recurse.
    			alreadyMatched.put(f, g);
    			if (findFirstApproxMatch(target, fragment, alreadyMatched)) {
    				return true;
    			}
    			alreadyMatched.remove(f);
    		}
    	}
    	return false;
    }

    private double tolerance(double edges) {
    	if (edges < 2) {
    		return 1.0;
    	} else if (edges < 3) {
    		return 0.5;
    	} else {
    		return (0.3 / edges) + 0.2;
    	}
    }
}
